package com.steve.combat.algorithm.douyin;

/**
 * @Author: STEVE
 * @Description: 找绝对众数 - Moore投票算法
 * @since: 2025-04-17
 */
public class MajorityElement {

    // 这种方法不需要使用额外的空间，只需要遍历数组两次。
    // 第一次遍历找出候选众数，第二次遍历验证这个候选众数是否真的是众数。
    public static int findMajorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        // 需要验证候选众数是否真的是众数（可选步骤，如果数组长度足够大，通常可以省省略）
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }

        if (count > nums.length / 2) {   // 检查是否真的是众数
            return candidate;
        } else {
            throw new IllegalArgumentException("No mahority element found");
        }
    }

    public static void main(String[] args) {
        int[] nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};
        try {
            System.out.println("The majority element is: " + findMajorityElement(nums));
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage()); // 处理没有众数的情况
        }
    }

}
